package com.yangjiayu.algorithm.array;

import java.util.HashMap;
import java.util.Map;

public class twoSum {
    //好比相亲，有且只有一对是真爱

    //一个个试
    //方法一：暴力法，穷举所有两数组合 时间复杂度O(n^2)排列组合C2n 空间复杂度O(1)
    public int[] twoSum1(int[] nums,int target){
        int n = nums.length;
        //双重for循环
        for(int i = 0;i<n - 1;i++){
            for(int j = i+1;j<n;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        //如果找不到，返回{-1,-1} 抛出异常也可以 throw new IllegalArgumentException("No two sum solution");
        return new int[]{-1,-1};
    }

    //我们可以把来的人都登记一下 使用map来做登记 两个for循环 O(n) 空间换时间 空间复杂度O(n)
    //方法二：哈希表保存所有数的信息
    public int[] twoSum2(int[] nums,int target){
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();

        //1.遍历数组，将数据全部保存入hash表
        for(int i = 0;i<nums.length;i++){
            map.put(nums[i],i);
        }

        //2.再次遍历数组，寻找每个数对应的哪个数是否存在
        for(int i = 0;i<nums.length;i++){
            int thatNum = target - nums[i];
            //如果哪个数存在,并且不是自己,就直接返回结果
            if(map.containsKey(thatNum) && map.get(thatNum)!=i){
                return new int[]{i,map.get(thatNum)};
            }
        }
        //如果找不到
        return new int[]{-1,-1};

        //问题？如果是相同能解决吗？，比如：{3，3} target=6 会产生覆盖 但是因为只有两个数所以也是对的。
        /*
        在Java的HashMap中，键（key）是唯一的。如果多次向同一个键（key）存入不同的值（value），后存入的值会覆盖之前的值。这是HashMap的核心特性。以下通过具体例子解释为什么代码能正确处理重复元素（如{3, 3}和target=6）：

场景还原：{3, 3}，target=6
1. 第一次遍历（存入HashMap）
i=0时，存入map.put(3, 0) → 键值对：3 → 0
i=1时，存入map.put(3, 1) → 键值对：3 → 1（覆盖之前的3 → 0）
此时HashMap中只有键3对应的索引是1。

2. 第二次遍历（查找补数）
处理第一个元素nums[0]=3：
需要的补数是6 - 3 = 3。
检查map中是否存在键3 → 存在。
检查map.get(3) != i → 1 != 0 ✔️。
返回结果[0, 1]。
为什么能解决问题？
关键点1：覆盖不影响结果
虽然第一个3的索引0被覆盖了，但你需要的是两个不同位置的元素。当处理第一个3（索引0）时，map中保存的是第二个3的索引1，此时两者恰好满足条件。

关键点2：依赖遍历顺序
第二次遍历是基于原始数组的顺序，逐个检查每个元素。
只要数组中存在一对重复元素（比如{3,3}），当处理第一个元素时，map中必然保存的是第二个元素的索引（因为覆盖发生在存入时）。
如果有更多重复元素？
假设数组是{3, 3, 3}，target=6：

第一次遍历存入HashMap：
最终map中保存的是最后一个3的索引2。
第二次遍历：
处理第一个3（索引0）→ 补数3存在，且2 != 0 → 返回[0, 2]。
处理第二个3（索引1）→ 补数3存在，且2 != 1 → 返回[1, 2]。
覆盖并不影响找到正确解，因为代码只需要找到任意一对有效解。

总结
键唯一性导致覆盖：HashMap的键必须唯一，重复存入会覆盖之前的值。
不影响解的正确性：因为第二次遍历时，map中保存的是最后一次出现的索引，而遍历顺序确保了至少有一个元素能正确匹配（尤其是重复元素的场景）。
避免自匹配：通过条件map.get(thatNum) != i确保不会使用同一个元素两次。
因此，即使存在重复元素，代码仍能正确返回结果。覆盖的特性在这个问题中反而帮助简化了逻辑

         */
    }


    //改进：遍历一次hash表，空间复杂度O(1)
    public int[] twoSum3(int[] nums,int target) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i<n;i++){
            int thatNum = target - nums[i];
            if(map.containsKey(thatNum) && map.get(thatNum)!=i){
                return new int[]{map.get(thatNum),i};//往前找 所以i在后
            }
            map.put(nums[i],i);
        }
        return new int[]{-1,-1};

    }


    public static void main(String[] args) {
        int[] input = {2,7,11,15};
        int target = 9;
        //可以定义一个大数组，进行性能调试

        //为了计算程序运行时间，开始计算和计算完成分别计时
        long startTime = System.currentTimeMillis();
        System.out.println("程序开始运行");

        twoSum ts = new twoSum();
        int[] result = ts.twoSum3(input, target);
        System.out.println("程序运行结束");
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间："+(endTime-startTime)+"ms");
        System.out.println(result[0]+","+result[1]);
    }

}
